package dp;

import java.util.Arrays;

public class LC322 {
    public int coinChange(int[] coins, int amount) {
        //如果钱数=0，返回0
        if(amount==0) return 0;
        //如果钱数<0，返回0
        if(amount<0) return -1;
        //创建一个数组长度为amount+1的数组，钱数=0的状态也需要保存，以便后续使用
        int[] dp=new int[amount+1];
        //因为要求最小值，所以将数组初始化为数组取不到的值
        Arrays.fill(dp,amount+1);
        //当钱数=0时，需要的硬币数量也为0
        dp[0]=0;
        for(int i=0;i<dp.length;i++){
            for(int coin : coins){
                if(i-coin<0) continue;
                // dp[i]有两种实现的方式，
                // 一种是包含当前的coin,那么剩余钱就是 i-coin,这种操作要兑换的硬币数是 dp[i-coin](剩余钱数所需的硬数) + 1 (当前coin需要一个硬币)
                // 另一种就是不包含，要兑换的硬币数是memo[i]
                dp[i]=Math.min(dp[i],1+dp[i-coin]);
            }
        }
        //若是amount的值仍是初始化时的值，那么说明无法凑够这个零钱，返回-1
        return (dp[amount]==amount+1)?-1:dp[amount];
    }
}

